//我们称一个数字字符串是 好数字 当它满足（下标从 0 开始）偶数 下标处的数字为 偶数 且 奇数 下标处的数字为 质数 （2，3，5 或 7）。 
//
// 
// 比方说，"2582" 是好数字，因为偶数下标处的数字（2 和 8）是偶数且奇数下标处的数字（5 和 2）为质数。但 "3245" 不是 好数字，因为 3 
//在偶数下标处但不是偶数。 
// 
//
// 给你一个整数 n ，请你返回长度为 n 且为好数字的数字字符串 总数 。由于答案可能会很大，请你将它对 10⁹ + 7 取余后返回 。 
//
// 一个 数字字符串 是每一位都由 0 到 9 组成的字符串，且可能包含前导 0 。 
//
// 
//
// 示例 1： 
//
// 
//输入：n = 1
//输出：5
//解释：长度为 1 的好数字包括 "0"，"2"，"4"，"6"，"8" 。
// 
//
// 示例 2： 
//
// 
//输入：n = 4
//输出：400
// 
//
// 示例 3： 
//
// 
//输入：n = 50
//输出：564908303
// 
//
// 
//
// 提示： 
//
// 
// 1 <= n <= 10¹⁵ 
// 
//
// Related Topics 递归 数学 👍 49 👎 0


package LeetCode.editor.cn;

/**
 * @author ldltd
 * @date 2025-04-13 18:12:20
 * @description 1922.统计好数字的数目
 */
public class CountGoodNumbers{
	 public static void main(String[] args) {
	 	 //测试代码
	 	 CountGoodNumbers fun=new CountGoodNumbers();
	 	 Solution solution = fun.new Solution();
		 System.out.println((3*4*5)%12);
		 System.out.println(((((3%12)*4)%12)*5)%12);
		 System.out.println(5*4*5*4);
	 }
	 
//力扣代码
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
		 int mod= (int) 1e9+7;
    //奇数位有 2 3 5 7
	//偶数位除了最高位，有 0 2 4 6 8
	//最高位有2 4 6 8
	//答案就是  5*4*5*4*5*4……最后*4
	//偶数个就是 5*4*5*4
	//奇数个就是 5*4*5*4*4
	//但是最高有 10^15位置，所以问题转换为怎么存这么长的数字
	//还可以用计网的慢开始，快速幂的相关计算优化

	// 每次两位算一个 20，最后剩 1 位时再乘 5
	public int countGoodNumbers(long n) {
		if (n == 1) return 5;
		return (int) fastHelper(n);
	}

	// 正确的快速幂写法，base = 20，每次乘两位
	private long fastHelper(long n) {
		long res = 1;
		long base = 20; // 每两个位置有 4*5 种组合
		long exp = n / 2;
		while (exp > 0) {
			if ((exp & 1) == 1) {
				res = res * base % mod;
			}
			base = base * base % mod;
			exp >>= 1;
		}

		// 如果是奇数长度，还要额外乘一次 5（表示偶数位）
		if ((n & 1) == 1) {
			res = res * 5 % mod;
		}

		return res;
	}
	public int countGoodNumbers2(long n) {
		if (n == 1) return 5;
	//奇数偶数算成一组两位20个
		long res = 1;
		long groupSize = 1;  // 初始处理1组（2位）
		long groupValue = 20; // 每组的值（5*4）

		// 处理完整的2位组
		while (n > 1) {
			if (groupSize > n / 2) {
				groupSize = 1;
				groupValue = 20;
			}

			long groups = n / 2 / groupSize;
			if (groups > 0) {
				res = (res * fastPow(groupValue, groups)) % mod;
				n -= 2 * groupSize * groups;
			}

			groupSize *= 2;
			groupValue = (groupValue * groupValue) % mod;
		}

		// 处理最后剩余的一位（如果有）
		if (n == 1) {
			// 判断最后一位是奇数位还是偶数位
			// 总长度如果是奇数，则最后一位是偶数位（下标从0开始）
			res = (res * 5) % mod; // 偶数位可以选择0,2,4,6,8
		}

		return (int) res;
	}

	public int countGoodNumbers1(long n) {
		long evenCount = (n + 1) / 2;  // 偶数下标数量
		long oddCount = n / 2;         // 奇数下标数量
		long part1 = fastPow(5, evenCount);  // 偶数位的可能性
		long part2 = fastPow(4, oddCount);    // 奇数位的可能性
		return (int) ((part1 * part2) % mod);
	}

	// 快速幂算法
	private long fastPow(long x, long n) {
		long res = 1;
		while (n > 0) {
			if ((n & 1) == 1) {
				res = (res * x) % mod;
			}
			x = (x * x) % mod;
			n >>= 1;
		}
		return res;
	}
}
//leetcode submit region end(Prohibit modification and deletion)

}
